

			PETRECERE
		       -----------

	Imaginati-va ca luati parte la o petrecere la care participa cel mult 500 de persoane. Gazda
ii invita pe toti la cina. In sufragerie exista mai multe mese. Invitatii se aseaza la masa in modul
urmator: fiecare persoana care nu sta singura la masa trebuie sa cunoasca cel putin o persoana de
la masa respectiva. Se presupune ca daca o persoana o cunoaste pe a doua, atunci si a doua o cu-
noaste pe prima.
	Asezarea la mese nu este insotita de prezentari. Drept urmare, daca doua persoane situate
la aceeasi masa nu se cunosteau initial, ele nu se vor cunoaste nici dupa asezarea la masa.

	a) Determinati numarul minim de mese necesare persoanelor care sunt asezate la fiecare masa.
	
	La fiecare masa exista o unica persoana care va vorbi cu chelnerul; aceasta persoana este
numita liderul mesei. Fiecare persoana transmite tuturor persoanelor situate la aceeasi masa op-
tiunea sa privind meniul. Timpul necesar fiecarei persoane de a transmite optiunea sa tuturor per-
soanelor pe care le cunoaste este constanta si aceeasi pentru fiecare persoana.
	b) Determinati pentru fiecare masa persoana cea mai indicata ca lider, astfel incat aceasta
sa primeasca optiunile in timp minim; listati pentru fiecare masa liderul ales si timpul corespun-
zator.

	Dupa masa gazda doreste sa uneasca mesele. In acest scop, el cheama cativa prieteni. Fie-
care dintre acestia, la sosirea sa, este prezentat liderilor a doua mese, dupa care mesele sunt
unite formand o noua masa, al carei lider devine.
	c) Care ste ordinea de unire a meselor astfel incat in final toate mesele sunt unite in-
tr-una singura si conditiile de punctul b) sunt satisfacute? Specificati timpul minim necesar li-
derului mesei finale pentru a primi informatii de la toate celelalte persoane.

	Dupa unirea meselor, prietenii gazdei se retrag si mesele isi recapata structura de dinain-
te de unire pana la terminarea cinei. Cand cina se termina, persoanele incep sa paraseasca mesele.
	d) Determinati, pentru fiecare masa, numarul minim de persoane si ordinea in care acestea
parasesc masa, pana cand persoanele care au  mai ramas se cunosc intre ele.

EXEMPLU:
	Sa presupunem ca numarul persoanelor este opt si ca:
- pers.1 cunoaste pers. 2 si 3
- pers.2 cunoaste pers. 1 si 4
- pers.3 cunoaste pers. 1 si 4
- pers.4 cunoaste pers. 2 si 3
- pers.5 cunoaste pers. 6
- pers.6 cunoaste pers. 5 si 7
- pers.7 cunoaste pers. 6
- pers.8 nu cunoaste nici o alta persoana

Un set de date corect are forma:
8
1 2
1 3
2 4
7 6
4 4
5 6
0 0

O iesire corecta are forma:
a)
3 mese
Masa 1: 1 2 3 4
Masa 2: 5 6 7
Masa 3: 8
b)
lideri:
Masa 1: 2 timp=2
Masa 2: 6 timp=1
Masa 3: 8 timp=0
c)
6 8 Noul lider: 9
2 9 Noul lider: 10
Timp=3
d)
Persoanele care pleaca:
Masa 1: 2 3
Masa 2: 6
Masa 3: